/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    void invertBinaryTree(TreeNode * root) {
        // write your code here
        if( root == NULL ){
            return;
        }

        invert(root);
    }

    void invert(TreeNode *node){
        TreeNode *left = node->left;
        TreeNode *right = node->right;
        node->right = left;
        node->left = right;
        
        if( left )
            invert(left);
        if( right )
            invert(right);
    }
};

class Solution {
public:
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    void invertBinaryTree(TreeNode * root) {
        // write your code here
        if( root == NULL ){
            return;
        }
        TreeNode *left= NULL;
        TreeNode *right = NULL;
        TreeNode *p = NULL;

        vector<TreeNode *> node;
        node.push_back(root);
        int size = 0;

        while( !node.empty() ){
            size = node.size();
            while( size-- ){
                p = node.back();
                node.pop_back();
                left = p->left;
                right = p->right;
                if( left )
                    node.push_back(left);
                if( right )
                    node.push_back(right);
                p->left = right;
                p->right = left;
            }
        }        
    }
};